// https://leetcode.cn/problems/JEj789/description/

// 算法思路总结：
// 1. 使用三个变量动态维护前一行的最小成本
// 2. 逐行计算当前行的三种颜色粉刷成本
// 3. 选择相邻不同颜色的最小成本组合
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int minCost(vector<vector<int>>& costs) 
    {
        int m = costs.size();
        int prev0 = 0, prev1 = 0, prev2 = 0;
        int cur0, cur1, cur2;

        for (int i = 0 ; i < m ; i++)
        {
            cur0 = min(prev1, prev2) + costs[i][0];
            cur1 = min(prev0, prev2) + costs[i][1];
            cur2 = min(prev0, prev1) + costs[i][2];

            prev0 = cur0;
            prev1 = cur1;
            prev2 = cur2;
        }
        return min({cur0, cur1, cur2});
    }
};

int main()
{
    vector<vector<int>> vv1 = {{17,2,17}, {16,16,5}, {14,3,19}};
    vector<vector<int>> vv2 = {{7,6,2}};

    Solution sol;
    cout << sol.minCost(vv1) << endl;
    cout << sol.minCost(vv2) << endl;

    return 0;
}